package srcInterviewPrep;

import java.util.ArrayList;

public final class MergeSort
{
    public static ArrayList<Integer> Sort(ArrayList<Integer> arr, int start, int end)
    {
        if (start == end)
        {
            ArrayList<Integer> list = new ArrayList<Integer>();
            list.add(arr.get(start));
            return list;
        }
        
        int mid = (start + end)/2;
        ArrayList<Integer> left = Sort(arr, start, mid);
        ArrayList<Integer> right = Sort(arr, mid + 1, end);
        return Merge(left, right);
    }
    
    private static ArrayList<Integer> Merge(ArrayList<Integer> left, ArrayList<Integer> right)
    {
        int pos1 = 0;
        int pos2 = 0;
        
        ArrayList<Integer> list = new ArrayList<Integer>(left.size() + right.size());
        
        while (pos1 < left.size() && pos2 < right.size())
        {
            if (left.get(pos1) <= right.get(pos2))
            {
                list.add(left.get(pos1));
                ++pos1;
            }
            else
            {
                list.add(right.get(pos2));
                ++pos2;
            }
        }
        
        if (pos1 < left.size())
        {
            AddRemainingElements(list, left, pos1);
        }
        
        if (pos2 < right.size())
        {
            AddRemainingElements(list, right, pos2);
        }
        
        return list;
    }
    
    private static void AddRemainingElements(
        ArrayList<Integer> mainList,
        ArrayList<Integer> smallList,
        int startIndex)
    {
        while (startIndex < smallList.size())
        {
            mainList.add(smallList.get(startIndex));
            ++startIndex;
        }
    }
}
